// https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/

// 算法思路总结：
// 1. 回溯算法计算所有子集异或和的总和
// 2. 维护当前路径的异或值，遍历所有子集
// 3. 在每个递归层级累加当前异或值到结果
// 4. 通过异或操作的特性进行回溯（a^b^b = a）
// 5. 时间复杂度：O(2ⁿ)，空间复杂度：O(n)（递归栈深度）

#include <iostream>
using namespace std;

#include <cstring>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    int ret = 0;
    int path = 0;
    int subsetXORSum(vector<int>& nums) 
    {
        ret = 0, path = 0;
        dfs(0, nums);

        return ret;
    }

    void dfs(int pos, vector<int>& nums)
    {
        ret += path;
        for (int i = pos ; i < nums.size() ; i++)
        {
            path ^= nums[i];
            dfs(i + 1, nums);
            path ^= nums[i];
        }
    }
};

int main()
{
    vector<int> nums1 = {1, 3};
    vector<int> nums2 = {5, 1, 6};

    Solution sol;

    cout << sol.subsetXORSum(nums1) << endl;
    cout << sol.subsetXORSum(nums2) << endl;

    return 0;
}